home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_100 / 183_01 / gray.c < prev    next >
Text File  |  1980-01-01  |  7KB  |  181 lines
  1. /* Some useful bit manipulation functions inspired by the article
  2.  * "Binary Magic Numbers" by Edwin E. Freed in DDJ #78, April 1983.
  3.  * by Dale Wilson, 1983  --- placed in the Public Domain
  4.  *
  5.  * These functions were written so thay may be directly translated
  6.  *  into assembly language for most computers.
  7.  *
  8.  * These functions were tested on a Zenith 100 computer using the
  9.  * C86 compiler from Computer Innovations, Inc.
  10.  *
  11.  * --------------------------------------------------------------------
  12.  * This code was keyboarded into an IBM PC from the March'84 (#89) issue
  13.  * of Dr. Dobb's Journal.  The code was tested then on the IBM PC using
  14.  * the C86 compiler from Computer Innovations, Inc.  The output test
  15.  * results checked out with the sample output in the article.
  16.  * --------------------------------------------------------------------
  17.  */
  18. #include <stdio.h>
  19.  
  20. #define TRUE 1    /* true */
  21. #define FALSE 0 /* false */
  22. #define CNTLZ 26 /* ms-dos eof */
  23.  
  24. #define N 16   /* bits per "word" */
  25. #define V 4    /* log 2 of N      */
  26.  
  27. /* Since C does not have binary constants, the binary magic numbers are
  28.  * expressed below in hexadecimal.  B from Freed's article is devided
  29.  * into b1 and b2 since ther was no good reason to have them in the
  30.  * same array.
  31.  */
  32.  
  33. unsigned int b1[V] = { 0x5555, 0x3333, 0x0f0f, 0x00ff };
  34. unsigned int b2[V] = { 0xaaaa, 0xcccc, 0xf0f0, 0xff00 };
  35.  
  36. /* Converting binary numbers to Gray code is so simple that it may
  37.  * be best defined as a macro rather than a function.
  38.  */
  39.  
  40. #define binary_to_Gray(x) (x ^ x >> 1)     /* X exclusive or X shifted right 1 */
  41.  
  42. /* MAIN rutine to test the functions.
  43.  * Numbers ( entered in hexadecimal ) will be used as aguments in each
  44.  * of the functions.  As an additional check, the binary number resulting
  45.  * from the Gray_to_binary function will be converted back to Gray code --
  46.  * which shold result in the original number.
  47.  */
  48.  
  49. main(argc,argv)   int argc; char *argv[];
  50. {     unsigned int r,i;
  51.       int c;
  52.       while (TRUE)
  53.       {
  54.      printf("Enter number : ");
  55.      fscanf(stdin,"%x",&i);         /* read a hexadecimal */
  56.      while((c=getchar()) != '\n')   /* discard end of line */
  57.           if(c == EOF || c == CNTLZ)  /* except on end of file */
  58.            exit();        /*   quit */
  59.      printf("low clear bit: %d\n", low_clear_bit(i));
  60.      printf("high set bit : %d\n", hi_set_bit(i));
  61.      printf("side sum     : %d\n", side_sum(i));
  62.      printf("parity       : %d\n", parity(i));
  63.      r = Gray_to_binary(i);
  64.      printf("Gray code    : 0x%04x\n", r);
  65.      printf("GTB to Binary: 0x%04x\n", binary_to_Gray(r));
  66.      printf("Reversed bits: 0x%04x\n", reverse_bits(i));
  67.      putchar('\n');                 /* leave a blank line between */
  68.       }
  69. }
  70.  
  71. /* This function returns the bit number of the lowest bit in the word
  72.  * which is clear (zero).  The least significant bit is numbered 0, the
  73.  * bit to the left of that, 1, and so on...
  74.  * A minus 1 is returned for words in which all bits are on.
  75.  * The time to execute this function is proportional to V which is
  76.  * log2 of the number of bits in a word.
  77.  * Note that the function low_set_bit may be created by complementing the
  78.  * argument and calling low_clear_bit.
  79.  */
  80. low_clear_bit(value)   unsigned int value;
  81. {   unsigned int temp;
  82.     int i, result;
  83.     if((value = ~value) == 0)           /* complement, test for zero */
  84.      result = -1;               /*  zero means no clear bits */
  85.     else
  86.     {     result = 0;
  87.      for(i = V-1; i >= 0; i--)
  88.      {    result <<= 1;           /* make space for next bit */
  89.           temp = value & b1[i];    /* test using magic numbers */
  90.           if(temp == 0)
  91.            result |= 1;        /* next bit of result is 1 */
  92.           else
  93.            value = temp;       /* discard disqualified bits */
  94.      }
  95.     }
  96.     return(result);
  97. }
  98.  
  99. /* This function returns the bit number of the highest bit in the word
  100.  * which is set (one).    The least significant bit is numbered 0, the
  101.  * bit to the left of that, 1, and so on ...
  102.  * A minus 1 is returned for words in which all bits are off.
  103.  * The time to execute this function is proportinal to V which is
  104.  * log2 of the number of bits in a word.
  105.  * Note that the function high_clear_bit may be created by complementing the
  106.  * argument and calling high_set_bit.
  107.  */
  108. hi_set_bit(value)   unsigned int value;
  109. {   unsigned int temp;
  110.     int result, i;
  111.     if(value == 0)               /* if no bits are on  */
  112.      result = -1;               /*  return that info  */
  113.     else
  114.     {     result = 0;
  115.      for(i = V-1; i >= 0; i--)
  116.      {    result <<= 1;           /* space for next bit */
  117.           temp = value & b2[i];
  118.           if(temp != 0)
  119.           {    result |= 1;        /* next bit is one    */
  120.            value = temp;       /* discarded unneeded bits */
  121.           }
  122.      }
  123.     }
  124.     return(result);
  125. }
  126.  
  127. /* This function returns a count of the number of bits which are on in a
  128.  * word.  It executes in a time porportional to V, the log base 2 of the
  129.  * number of bits in a word.
  130.  * Note that a count of the number of zero bits in the word may be found
  131.  * by complementing the value and calling side_sum.
  132.  */
  133. side_sum(value)    unsigned int value;
  134. {   int i;
  135.     unsigned int s;
  136.     s = 1;
  137.     for(i=0; i<V; i++)          /* use magic in reverse order */
  138.     {     value = (value & b1[i]) + ((value >> s) & b1[i]);
  139.      s <<= 1;          /* generate the powers of two on the fly */
  140.     }
  141.     return(value);
  142. }
  143.  
  144. /* This function converts a number expressed in Gray code to the
  145.  * equivalent binary number.  It executes in time proportional to the
  146.  * log base 2 of the number of bits in the word.
  147.  */
  148. Gray_to_binary(value)    unsigned int value;
  149. {   unsigned int s;
  150.     for(s = N >> 1; s != 0; s >>= 1)
  151.     {     value ^= value >> s;
  152.     }
  153.     return(value);
  154. }
  155.  
  156. /* This function returns the parity of a word--that is, it returns a zero
  157.  * if the number of one bits in the word is even, and a one if the number
  158.  * of one bits in the word is odd.  The low order bit of the results of
  159.  * Gray_to_binary and side_sum both have this property, so isolating this
  160.  * bit gives the desired result.  Gray_to_binary was selected since it is
  161.  * a faster function that side_sum.
  162.  */
  163. parity(value)       unsigned int value;
  164. {
  165.     return(Gray_to_binary(value) & 1);     /* buld on previous work */
  166. }
  167.  
  168. /* This function reverses the bits in a word.  Strangly enough, this turns
  169.  * out to be a very useful function to have available.    Note that this function
  170.  * works only on functions with word lengths which are powers of 2.
  171.  */
  172. reverse_bits(value)  unsigned int value;
  173. {   unsigned int s,i;
  174.     s = 1;             /* s provides the powers of 2 */
  175.     for (i=0; i<V; i++)
  176.     {     value = ((value << s) & b2[i]) | ((value >> s) & b1[i]);
  177.      s <<= 1;
  178.     }
  179.     return(value);
  180. }
  181.